package com.csx.hashcode;

import java.util.TreeMap;

/**
 * @author 陈胤训
 * @date 2019/6/20 17:33
 * Utils: Intellij Idea
 * Description: 哈希表
 */
public class HashTable<K extends Comparable, V> {

    /**
     * 红黑树
     */
    private TreeMap<K, V>[] hashTable;

    /**
     * 哈希表大小
     */
    private int M;

    /**
     * 已经使用的大小
     */
    private int size;

    /**
     * 上界
     */
    private static final int  upperTol = 10;

    /**
     * 下界
     */
    private static final int  lowerTol = 2;

    /**
     * 初始大小
     */
    private static final int  initCapacity = 10;


    public HashTable(int M) {
        this.M = M;
        size = 0;
        this.hashTable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
    }

    public HashTable() {
        this(initCapacity);
    }

    /**
     * 辅助方法  得到哈希值
     * @param key 值
     * @return 哈希值
     */
    private int hash(K key){
        System.out.println((key.hashCode() & 0x7fffffff)% M);
        return (key.hashCode() & 0x7fffffff) % M;
    }

    /**
     * 获取已经使用的大小
     * @return 已经使用的大小
     */
    public int getSize(){
        System.out.println(M);
        return size;
    }

    public void add(K key, V value){
        if (hashTable[hash(key)].containsKey(key)){
            hashTable[hash(key)].put(key, value);
        }else{
            hashTable[hash(key)].put(key, value);
            size ++;

            if (size >= upperTol * M){
                resize(2 * M);
            }
        }
    }

    /**
     *  扩容
     * @param newM 新的M
     */
    private void resize(int newM) {
        TreeMap<K, V>[] treeMaps = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            treeMaps[i] = new TreeMap<>();
        }

        int oldM = M;
        this.M = newM;
        for (int i = 0; i < oldM ; i++) {
            TreeMap<K, V> map = hashTable[i];
            for (K key : map.keySet()){
                treeMaps[hash(key)].put(key, map.get(key));
            }
        }

        this.hashTable = treeMaps;
    }

    public V remove(K key){
        TreeMap<K, V> kvTreeMap = hashTable[hash(key)];
        V ret = null;
        if (kvTreeMap.containsKey(key)){
            ret = kvTreeMap.remove(key);
            size --;

            if (size < lowerTol * M && M / 2 >= initCapacity){
                resize(M / 2);
            }
        }
        return ret;
    }

    public void set(K key, V value){
        TreeMap<K, V> kvTreeMap = hashTable[hash(key)];
        if (!kvTreeMap.containsKey(key)){
            throw new IllegalArgumentException(key + " 不存在");
        }
        kvTreeMap.put(key, value);
    }

    public boolean contains(K key){
        return  hashTable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashTable[hash(key)].get(key);
    }

    public static void main(String[] args) {
        HashTable<String, Integer> hashTable = new HashTable();
        for (int i = 0; i < 300; i++) {
            hashTable.add("a" + i, i);
        }
        System.out.println(hashTable.getSize());
    }
}
